package Graph.graphWithWeight.ShortestPath.Dijkstra;

import Graph.graphWithWeight.GraphWeight;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @Author: 蔡翔
 * @Date: 2020/3/2 14:04
 * @Version 1.0
 * 时间复杂度 V2
 */
public class Dijkstra {
    private GraphWeight G;
    //源点s
    private int s;
    private int[] dis;
    private boolean[] visited;
    private int[] pre;

    //因为Node 这个类是要放到优先队列里面去的，所以要用来比较，所以要实现
    private class Node implements Comparable<Node>{
        //v 表示顶点序号，dis表示当前找到的 原点到v 的长度，也就是dis[v]
        public int v,dis;
        public Node(int v,int dis){
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node o) {
            return this.dis-o.dis;
        }
    }

    public Dijkstra(GraphWeight G,int s){
        this.G = G;
        G.validateVertex(s);
        this.s = s;
        dis = new int[G.V()];
        Arrays.fill(dis,Integer.MAX_VALUE);

        pre=new int[G.V()];

        dis[s] = 0;
        pre[s] = s;
        visited = new boolean[G.V()];

        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        //先把原点 add 进去。
        pq.add(new Node(s,0));

        while (!pq.isEmpty()){
            //找出最小dis[v] 是比较影响性能的 ，可以引入优先队列降低时间复杂度
            /*int curdis = Integer.MAX_VALUE;
            int cur = -1;
            //第一次遍历就是为了找到s ，原点
            //后续遍历 就是为了找出 source-i  最小的
            for(int v=0;v<G.V();v++){
                if(!visited[v] && dis[v]<curdis){
                    curdis = dis[v];
                    cur = v;
                }
            }*/

            //队首元素就是 dis【v】 值最小的顶点。
            int cur = pq.remove().v;
            //可能就是一条重复变
            if(visited[cur]){
                continue;
            }
            visited[cur] = true;
            for(int w:G.adj(cur)){
                //这里除了构建 空白点 之外， 在每次新加入点之后 还会动态的更新 现在到达这个点是否比之前更优
                if(!visited[w]){
                    if(dis[cur]+G.getWeight(cur,w)<dis[w]){
                        dis[w] = dis[cur]+G.getWeight(cur,w);
                        //每次更新 ，说明 会有新边生成 所以这里录到优先队列里面去，但是有一个缺点 之前不要的边还存在，
                        // 但是没关系，就算下次从队列中取出之前的边 也不会用了，因为visited[w] = true 了
                        //因为优先队列是可比较的，Node 又实现了Comparable接口 所以队首元素就是最小值
                        pq.add(new Node(w,dis[w]));
                        pre[w] = cur;
                    }
                }
            }
        }
    }

    //判别v是否和 原点 相连
    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return visited[v];
    }

    //v到 source 的距离
    public int disTo(int v){
        G.validateVertex(v);
        return dis[v];
    }

    //返回一个可以迭代的对象   参数t 是终点
    public Iterable<Integer> path(int t){
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)){
            return res;
        }
        int cur = t;
        while (cur!=s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        GraphWeight g = new GraphWeight("gDjjkstra.txt");
        Dijkstra dijkstra = new Dijkstra(g,0);
        for(int v=0;v<g.V();v++){
            System.out.print(dijkstra.disTo(v)+ " ");
        }
        System.out.println(dijkstra.path(3));
    }
}
